package com.bolang.onlycode.demo;

import java.util.Arrays;

// 8>>2 8向右移两位 相当于8\2的2次方
// 递归 一个函数调用自身
public class MergeSort2 {
    /**
     *
     * @param arr  需要排序的数组
     * @param left  数组左下标
     * @param right 数组右下标
     * @param temp  临时数组
     */
    public static void mergeSort(int[] arr,int left,int right,int[] temp ){
        //什么时候不递归了呢，切分出来的数组有序
        // 什么时候有序，数组只有一个数字的时候
        // 左指针等于右指针，
        // 此时表明数组已经被分为一个数字了，它已经是有序的了
        if(left<right){
            // 算出传入数组的中间坐标
            int mid =(left+right)/2;
            // 递归这个数组的左半部，直到左边已经有序
            mergeSort(arr,left,mid,temp);
            // 当左半部已经有序时，递归左半部对应的右半部
            mergeSort(arr,mid+1,right,temp);
            //当左边和右边都有序时，对两个有序的数组进行排序
            mergeArray(arr,left,mid,right,temp);
        }

    }


    /**
     *  合并两个有序数组，数组里只有一个数字的算有序数组
     * @param arr  需要排序的数组，每次传进来的数组是同一个数组，只不过 left mid right 不一样
     *  arr[left]---arr[mid];arr[mid+1,right]这数组中的两端分别是有序的
     * @param left  数组左下标
     * @param mid   数组中间下标
     * @param right  数组右下标
     * @param temp  暂时存放的数组
     */
    public static void mergeArray(int[] arr,int left,int mid ,int right,int[] temp){
        // 定义s1为左边的起点，s2为右边的起点
        int s1=left,s2=mid+1;
        // 定义e1为左边的终点，s2为右边的终点
        int e1=mid,e2=right;
        // 定义每次从临时数组哪里开始排
        int i =left;
        // 循环比较两个有序数组的首位,直到比较完左边或者右边

        while(s1<=e1&&s2<=e2){
            // 如果左边小于右边，将左边放到临时数组内，并将指针指向左边下一个
            if(arr[s1]<=arr[s2]){
                temp[i++]=arr[s1++];
            }else {
                temp[i++]=arr[s2++];
            }
        }
        // 比较完毕，左边或者右边可能会有剩下的，需要考虑
        while (s1<=e1){
            temp[i++]=arr[s1++];
        }
        while (s2<=e2){
            temp[i++]=arr[s2++];
        }
        // 这里必须用到两个数组
        // 每次排完序后，临时数组必须回填arr数组对应的位置
        while (left<=right){
            arr[left]=temp[left];
            left++;
        }

    }

    public static void main(String[] args) {
        int[] ints ={5,9,7,10,3,2,1,10,9,13};
        int[] ints1 =new int[ints.length];
       mergeSort(ints,0,ints.length-1,ints1);
        System.out.println(Arrays.toString(ints1));
    }


}
